package com.example.offer.no0010a.impl;

import com.example.offer.no0010a.Solution;

/**
 * @author yumuhui <yumuhui@kuaishou.com>
 * Created on 2021-05-13
 */
public class SolutionImpl implements Solution {

    @Override
    public int fib(int n) {

        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

//        return fib(n - 1) + fib(n - 2);

        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = (p + q) % 1000000007;
        }
        return r;

//        int[] arr = new int[n + 1];
//        arr[0] = 0;
//        arr[1] = 1;
//        for (int i = 2; i <= n; i++) {
//            arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;
//        }
//        return arr[n];
    }
}
